package leetcode.editor.cn.q1_300.q50;

import java.util.*;

/**
 * @author qidi
 * @date 2021-12-08 09:43:38
 */
class Q0051_NQueens {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> indexList = new ArrayList<>();
            Set<Integer> col = new HashSet<>();
            Set<Integer> lDown = new HashSet<>();
            Set<Integer> rDowm = new HashSet<>();
            int[] qs = new int[n];
            Arrays.fill(qs, -1);
            process(0, n, col, lDown, rDowm, qs, indexList);

            return indexList;
        }

        private void process(int i, int n, Set<Integer> col, Set<Integer> lDown, Set<Integer> rDown, int[] qs, List<List<String>> indexList) {
            if (i == n) {
                List<String> inner = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    StringBuilder sb = new StringBuilder();
                    for (int k = 0; k < n; k++) {
                        if (k == qs[j]) {
                            sb.append("Q");
                        } else {
                            sb.append(".");
                        }
                    }

                    inner.add(sb.toString());
                }
                indexList.add(inner);
                return;
            }

            for (int j = 0; j < n; j++) {
                if (col.contains(j)) continue;

                if (lDown.contains(i - j)) continue;

                if (rDown.contains(i + j)) continue;

                qs[i] = j;
                col.add(j);
                rDown.add(j + i);
                lDown.add(i - j);

                process(i + 1, n, col, lDown, rDown, qs, indexList);

                qs[i] = -1;
                col.remove(j);
                rDown.remove(j + i);
                lDown.remove(i - j);
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0051_NQueens().new Solution();
        System.out.println(solution.solveNQueens(4));
    }
}